
//接雨水
class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> left_area(n);
        vector<int> right_area(n);

        int left_max=0,right_max=0;
        for(int i=0;i<n;i++)   //求从左向右的储水量
        {
            left_max=max(left_max,height[i]);
            left_area[i]=left_max-height[i];
        }
        for(int i=n-1;i>=0;i--)   //求从右向左的储水量
        {
            right_max=max(right_max,height[i]);
            right_area[i]=right_max-height[i];
        }

        int ret=0;
        for(int i=0;i<n;i++)  //取两个储水量的较小值即可
            ret+=min(right_area[i],left_area[i]);

        return ret;
    }
};